/* Compute levenshtein distance
 *
 * Original
 *
 * by Unknown author
 *
 * Adpated to UTF-8 encoding
 *
 * by ben "boin" bonoeil
 *
 */

#include <string.h>
#include <malloc.h>
#include <ctype.h>
#include "utf8simple.h"

static int Minimum (int a, int b, int c);
static int *GetCellPointer (int *pOrigin, int col, int row, int nCols);
static int GetAt (int *pOrigin, int col, int row, int nCols);
static void PutAt (int *pOrigin, int col, int row, int nCols, int x);

/*******************************/
/* Get minimum of three values */
/*******************************/

static int Minimum (int a, int b, int c)
{
  int m;
  m = (a < b) ? a : b;
  m = (m < c) ? m : c;
  return m;
}

/*****************************************************/
/* Get a pointer to the specified cell of the matrix */
/*****************************************************/

static int *GetCellPointer (int *pOrigin, int col, int row, int nCols)
{
  return pOrigin + col + (row * (nCols + 1));
}

/********************************************************/
/* Get the contents of the specified cell in the matrix */
/********************************************************/

static int GetAt (int *pOrigin, int col, int row, int nCols)
{
  int *pCell;
  pCell = GetCellPointer (pOrigin, col, row, nCols);
  return *pCell;
}

/**********************************************************/
/* Fill the specified cell in the matrix with the value x */
/**********************************************************/

static void PutAt (int *pOrigin, int col, int row, int nCols, int x)
{
  int *pCell;
  pCell = GetCellPointer (pOrigin, col, row, nCols);
  *pCell = x;
}

/********************************/
/* Compute Levenshtein distance */
/********************************/

int levenshtein_distance (const char *s, const char *t)
{
  int *d;            /* pointer to matrix */
  int n;             /* length of s */
  int m;             /* length of t */
  int i;             /* iterates through s */
  int j;             /* iterates through t */
  int s_i;           /* ith character of s */
  int t_j;           /* jth character of t */
  int cost;          /* cost */
  int result;        /* result */
  int cell;          /* contents of target cell */
  int above;         /* contents of cell immediately above */
  int left;          /* contents of cell immediately to left */
  int diag;          /* contents of cell immediately above and to left */
  int sz;            /* number of cells in matrix */

  const char * sp, * tp;



  /* Step 1 */
  n = strlen_utf8 (s);
  m = strlen_utf8 (t);
  if (n == 0) {
    return m;
  }
  if (m == 0) {
    return n;
  }
  sz = (n+1) * (m+1) * sizeof (int);
  d = (int *) malloc (sz);

  /* Step 2 */
  for (i = 0; i <= n; i++) {
    PutAt (d, i, 0, n, i);
  }

  for (j = 0; j <= m; j++) {
    PutAt (d, 0, j, n, j);
  }

  /* Step 3 */

  for (i = 1, sp=s; i <= n; i++) {

    s_i = getc_utf8(sp);
    sp += 1 + ((s_i>>29)&3);
    s_i &= (1<<29)-1;

    /* Step 4 */

    for (j = 1, tp=t; j <= m; j++) {

      t_j = getc_utf8(tp);
      tp += 1 + ((t_j>>29)&3);
      t_j &= (1<<29)-1;

      /* Step 5 */

      if (s_i == t_j) {
        cost = 0;
      } else if (toupper(s_i) == toupper(t_j)) {
        cost = 1;
      } else {
        cost = 2;
      }

      /* Step 6 */

      above = GetAt (d,i-1,j, n);
      left = GetAt (d,i, j-1, n);
      diag = GetAt (d, i-1,j-1, n);
      cell = Minimum (above + 1, left + 1, diag + cost);
      PutAt (d, i, j, n, cell);
    }
  }

  /* Step 7 */

  result = GetAt (d, n, m, n);
  free (d);
  return result;

}
